class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 0:
            return -1
        left = 0
        right = len(nums)-1
        if nums[right] < nums[left]:
            while left < right:
                if nums[left] == target:
                    return left
                if nums[right] == target:
                    return right
                mid = left+((right-left) >> 1)
                if nums[mid] == target:
                    return mid
                if nums[mid] < nums[left]:
                    right = mid
                elif nums[mid] > nums[right]:
                    left = mid+1
                else:
                    right = left
            if nums[len(nums)-1] > target and nums[left] < target:
                right = len(nums)-1
            elif nums[0] < target and left > 0 and nums[left-1] > target:
                right = left-1
                left = 0
            else:
                return left if nums[left] == target else -1
        while left < right:
            mid = left + ((right - left) >> 1)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid-1
            else:
                left = mid+1
        return left if nums[left] == target else -1



